Gradient Descent from MATH102

Contents

Gradient Descent from MATH102#

Open In Colab

import numpy as np
from scipy.integrate import solve_ivp
try:
    import plotly.graph_objects as go
except:
    !pip install plotly
    import plotly.graph_objects as go

Theory#

Oppgave 4. La \(f \colon \mathbb{R}^2 \to \mathbb{R}\) være deriverbar og la \(\mathbf{y}\colon \mathbb{R}\to \mathbb{R}^2\) være en deriverbar kurve slik at \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\). Forklar hvorfor funksjonen \(f(\mathbf{y}(t))\) ikke er voksende rundt noen \(t \in \mathbb{R}\).

Strategi: Hvis \(\mathbf{y}\) er som i oppgaven ovenfor, og nærmer \(\mathbf{y}(t)\) seg et punkt \(\mathbf{x}_0\) når \(t\) blir stor så er kanskje dette punktet et lokalt minimumspunkt for \(f\). Mange steder brukes dette til å søke etter lokale minimumspunkter for \(f\). Hvis vi klarer å finne et slik punkt \(\mathbf{x}_0\) kan vi bruke andrederiverttesten til å prøve å vise at det er et lokalt minimumspunkt.

Hvis vi er gitt et startpunkt \(\mathbf{y}_0\) kan vi prøve å finne en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) med startbetingelse \(\mathbf{y}(0) = \mathbf{y}_0\) og se hvilket punkt \(\mathbf{y}(t)\) går mot når \(t\) blir stor.

Lemma La \(f \colon \mathbb{R}^n \to \mathbb{R}\) være kontinuerlig deriverbar. Hvis \(\mathbf{y}(t)\) er en løsning til differensialligningen \(\mathbf{y}'(t) = -\nabla f(\mathbf{y}(t))\) og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) for en \(\mathbf{p} \in \mathbb{R}^n\), da er \(\nabla f(\mathbf{p}) = 0\)

Konsekvens: Siden \(f \circ \mathbf{y}\) ikke er voksende er \(\mathbf{p} = \lim_{t \to \infty} \mathbf{y}(t)\) enten et lokalt minimum eller et saddelpunkt, det vil si, et kritisk punkt for \(f\) som verken er et lokalt minimum eller et lokalt maksimum.

Forklaring: At \(f\) er kontinuerlig deriverbar betyr at funksjonen \(\mathbf{x} \mapsto \nabla f(\mathbf{x})\) er kontinuerlig.

Siden denne funksjonen er kontinuerlig og \(\lim_{t \to \infty} \mathbf{y}(t) = \mathbf{p}\) vet vi at

\[ \lim_{t \to \infty} \nabla f(\mathbf{y}(t)) = \nabla f(\lim_{t \to \infty} \mathbf{y}(t)) = \nabla f(\mathbf{p}).\]

Derfor er $\(\lim_{t \to \infty} (f \circ \mathbf{y})'(t) = \lim_{t\to \infty} \nabla f'(\mathbf{y}(t)) \cdot \mathbf{y}'(t) = \lim_{t\to \infty} -|\nabla f(\mathbf{y}(t))|^2 = -|\nabla f(\mathbf{p})|^2.\)$

Siden er \(f\) og \(\mathbf{y}\) er deriverbare er de også kontinuerlige.

Derfor er også \((f \circ \mathbf{y})\) kontinuerlig slik at \((f \circ \mathbf{y})(t) \to f (\mathbf{p})\) for \(t \to \infty\).

Derfor kan ikke \(\lim_{t \to \infty} (f \circ \mathbf{y})'(t)\) konvergere til et tall forskjellig fra null, slik at \(\nabla f(\mathbf{p}) = 0\) er eneste mulighet.

Eksempel#

\(f(x) = e^{-x_1^2 - x_2^2}\)

# @title Plotter

def f(x):
    x1, x2 = x
    # bemerk at hvis x ikke er i D, da lar vi f være ikke definert, eller nan for not a number
    return -np.exp(-x1**2 - x2**2)

def gradientf(x1, x2):
    return np.array(2*x1*np.exp(-x1**2 - x2**2), 2*x2*np.exp(-x1**2 - x2**2))

def dy(t, y):
    return -gradientf(y[0], y[1])

sol = solve_ivp(dy, t_span=[0, 100], y0=[0.5, 0.5], t_eval=np.linspace(0, 100, 1000))



# Create a grid of x and y values
x1 = np.linspace(-1, 1, 300)
x2 = np.linspace(-1, 1, 300)
#x1 = np.sign(x1) * np.sqrt(np.abs(x1))
#x2 = np.sign(x2) * np.sqrt(np.abs(x2))
x = np.meshgrid(x1, x2)

# Compute the function values
x3 = f(x)


# Create figure
fig = go.Figure()

# Add surface
fig.add_surface(
    x=x[0], y=x[1], z=x3, colorscale="Viridis", opacity=0.8
)

# Add curve
fig.add_scatter3d(
    x=sol.y[0], y=sol.y[1], z=f(sol.y), mode="lines", line=dict(color="red", width=10)
)

fig.show()
# @title Ny f

def f(x):
  x1, x2 = x
  return -(2*np.exp(-((x1 + 1)**2 + x2**2)) + np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2)))

def gradientf(x):
    x1 = x[0]
    x2 = x[1]
    return -np.array([-4*(x1 + 1)*np.exp(-(x1 + 1)**2 - x2**2) - 2*(x1 - 2)*np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2)),
            -4*x2*np.exp(-(x1 + 1)**2 - x2**2) - 2*(x2 - 0.2)*np.exp(-((x1 - 2)**2 + (x2 - 0.2)**2))])

def dy(t, y):
    return -gradientf(y)

sol = solve_ivp(dy, t_span=[0, 100], y0=[1.5, 0.5], t_eval=np.linspace(0, 100, 1000))
sol2 = solve_ivp(dy, t_span=[0, 100], y0=[.6, 0.5], t_eval=np.linspace(0, 100, 1000))


# Create a grid of x and y values
x1 = np.linspace(-2.5, 3.5, 300)
x2 = np.linspace(-1.5, 1.5, 300)
#x1 = np.sign(x1) * np.sqrt(np.abs(x1))
#x2 = np.sign(x2) * np.sqrt(np.abs(x2))
x = np.meshgrid(x1, x2)

# Compute the function values
x3 = f(x)


# Create figure
fig = go.Figure()

# Add surface
fig.add_surface(
    x=x[0], y=x[1], z=x3, colorscale="Viridis", opacity=0.8
)

# Add curve
fig.add_scatter3d(
    x=sol.y[0], y=sol.y[1], z=f(sol.y), mode="lines", line=dict(color="red", width=10)
)
fig.add_scatter3d(
    x=sol2.y[0], y=sol2.y[1], z=f(sol2.y), mode="lines", line=dict(color="red", width=10)
)

fig.show()

Vi vet at vi kan løse differensialligninger med Eulers metode. Hvis vi er ute etter å finne lokale kan vi spørre om hvor stor t skal være for at vi kommer tett på et lokalt minimum. I stedet for å gi t til algoritmen kan vi gi et kriterium for å stoppe når funksjonsverdien endrer seg lite. Rigger vi Eulers metode slik kalles den for “gradient descent”.

Oppgave

La \(f \colon \mathbb{R}^2 \to \mathbb{R}\) være funksjonen gitt ved

\[\begin{split}f\left(\begin{bmatrix}x\\y\end{bmatrix}\right) = \cos(x^2 + y^2).\end{split}\]
  1. Finn gradienten til \(f\).

  2. Plott grafen til \(f\).

  3. Finn et lokalt minimum til \(f\) ved å bruke gradient descent, startende i punktet \(\begin{bmatrix}1\\1\end{bmatrix}\).